package june7_13;

import datastructures.BST;
import datastructures.base.Node;


/**
 * Find the lowest common ancestor of two elements in BST
 *  - Assumed that x is smaller than y 
 * 	Time Complexity - O (logn) for balanced tree, O(n) for skewed tree
 * 
 * Find the lowest common ancestor of two elements in Binary Tree
 * 	- Do Inorder traversal	(common ancestor will lie between the two numbers in the outpur string)
 *  - Do Post order traversal 
 *  	For each of the number lie between x and y in the inorder traversal output, 
 *  	- note the index of the elements in post order traversal, the one at the right most end is the common ancestor
 * 	Time complexity - O(n)
 *   
 * @author udhaya
 *
 */
public class LowestCommonAncestor
{
	static StringBuffer inOrder = new StringBuffer ();
	static StringBuffer postOrder = new StringBuffer ();
	
	private static int lowestCommonAncestorBST (Node root, int x, int y)
	{
		
		// If the reached the leaf, the node does not exist
		if (root == null)
			return -1;

		if (root.data == x || root.data == y)
			return -1;

		// If any of the input node is child of the current node, we got the LCA
		if (root.right != null &&
				root.right.data == x || root.right.data == y)
			return root.data;
		
		if (root.left != null &&
				root.left.data == x || root.left.data == y)
			return root.data;
		
		if (root.data > x && root.data < y)
			return root.data;
		if (root.data > x && root.data > y)
			return lowestCommonAncestorBST (root.left, x, y);
		if (root.data < x && root.data < y)
			return lowestCommonAncestorBST (root.right, x, y);
		
		System.out.println ("It should not be reached");
		return -1;
	}
	
	
	static int lowestCommonAncestorOfBinaryTree (Node root, int x, int y)
	{
		inOrder.setLength (0);
		postOrder.setLength (0);
		
		inOrderTraversal (root);
		postOrderTraversal (root);
		
		String[] inOrderChars = inOrder.toString ().split (",");
		String[] postorderChars = postOrder.toString ().split (",");

		int xPos = -1, yPos = -1;
		int ancestor = -1;
		int index = -1;
		
		for (int i = 0; i < inOrderChars.length; i++)
		{
			// Until starting with x value in the inorder traversal - no need to proceed
			if (xPos == -1)
			{
				if (inOrderChars[i].equals ("" + x))
				{
					xPos = i;
				}
				continue;
			}

			// After Y position no need to proceed
			if (inOrderChars[i].equals ("" + y))
			{
				break;
			}

			//Get the element
			String elementToSearch = inOrderChars[i];

			//Find the index of the element in post order array
			index = indexOf(postorderChars, elementToSearch);
			
			//If the index is higher than the index of previous element, note the index as maximum
			if (index > ancestor)
				ancestor = index;
		}
		
		return Integer.valueOf (inOrderChars[ancestor]);
	}
	
	static int indexOf (String[] theList, String element)
	{
		for (int i= 0; i <theList.length; i++)
		{
			if (theList[i].equalsIgnoreCase (element))
				return i;
		}

		return -1;
	}
	
	static void inOrderTraversal (Node root)
	{
		if (root == null)
			return;
		
		inOrderTraversal (root.left);
		
		if (inOrder.length () != 0)
			inOrder.append (",");
		inOrder.append (root.data);
		
		inOrderTraversal (root.right);
	}

	static void postOrderTraversal (Node root)
	{
		if (root == null)
			return;
		
		postOrderTraversal (root.left);
		postOrderTraversal (root.right);
		
		if (postOrder.length () != 0)
			postOrder.append (",");
		postOrder.append (root.data);
	}

	public static void main (String [] args)
	{
		BST theTree = new BST();
		theTree.createNodes (new int[]{2, 1, 4, 3, 5});
		System.out.println ("LCA of BST : " + lowestCommonAncestorBST(theTree.root, 3, 4));
		
		
		Node root = new Node (2);
		root.left = new Node (1);
		root.right = new Node (4);
		root.right.left = new Node (3);
		root.right.right = new Node (5);
		
		System.out.println ("LCA of BT : " + lowestCommonAncestorOfBinaryTree (theTree.root, 3, 5));
	}
}
